package com.tengol.leetcode;

/**
 * 84. Largest Rectangle in Histogram (84. 柱状图中最大的矩形)
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 *
 * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 * 示例:
 *
 * 输入: [2,1,5,6,2,3]
 * 输出: 10
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *
 * 【解题思考过程】
 * 1. 未读懂题意，不知道如何与所学知识对应上
 * 2. 再次审视问题
 *    （1）面积最大是否意味着，相邻的、连续最大数字的子数组，也就是前 K 大的连续相邻的最大子数组，但 K 如何确定？
 *    （2）但如果是 [2,3,2,2,5,2,2,4,2,6]，面积最大就是宽度决定的，不再是高度
 *    （3）也就是说，最大面积，有可能是高度决定的（连续前 K 大的数字），也可能是宽度决定（连续最小的数字长）
 *
 * @author dongrui
 * @date 2020/05/30
 */
public class No84LargestRectangleInHistogram {
    public int largestRectangleArea(int[] heights) {

        return 0;
    }

    public static void main(String[] args) {
        No84LargestRectangleInHistogram histogram = new No84LargestRectangleInHistogram();
        int[] case1 = {2,1,5,6,2,3};
        int[] case2 = {2};
        int[] case3 = {2,8};
        int[] case4 = {2,9,2};
        int[] case5 = {2,3,2,2,5,2,2,4,2,6};
        int i = histogram.largestRectangleArea(case1);
        System.out.println(i);
    }
}
